#include <iostream>
#include <string>
#include <vector>

using namespace std;

// I	1
// V	5
// X	10
// L	50
// C	100
// D	500
// M	1000

class Solution
{
public:
    string intToRoman(int num)
    {
        string result;
        Code(result, num / 1000, '1', '2', 'M');
        Code(result, num / 100 % 10, 'M', 'D', 'C');
        Code(result, num / 10 % 10, 'C', 'L', 'X');
        Code(result, num % 10, 'X', 'V', 'I');
        return result;
    }

    void Code(string &result, int bit, char c10, char c5, char c1)
    {
        if (bit == 0)
        {
            return;
        }
        if (bit >= 5)
        {
            if (bit == 9)
            {
                result.push_back(c1);
                result.push_back(c10);
            }
            else
            {
                result.push_back(c5);
                for (int j = 0; j < bit - 5; j++)
                {
                    result.push_back(c1);
                }
            }
        }
        else
        {
            if (bit == 4)
            {
                result.push_back(c1);
                result.push_back(c5);
            }
            else
            {
                for (int j = 0; j < bit; j++)
                {
                    result.push_back(c1);
                }
            }
        }
    }
};

int main()
{
    cout << "Code12" << endl;
    Solution s;
    cout << s.intToRoman(3749);
    return 0;
}
//MMMDCCXLIX
//222DCCXLIX